package com.example.algorithm.linear.link;


import org.w3c.dom.Node;

/**
 * @program: algorithm
 * @description: 约瑟夫问题
 * @packagename: com.example.algorithm.linear.link
 * @author: Jay
 * @date: 2022/04/23 12:13:04
 **/
public class JosephTest {

    public static void main(String[] args) {
        //解决约瑟夫问题
        //1.构建循环链表，包含41个节点，分别存储1-41之间的值
        //首结点
        Node<Integer> first = null;
        //记录前一个节点
        Node<Integer> pre = null;

        for (int i = 1; i <= 41; i++ ){
            //如果是第一个节点
            if (i == 1){
                first = new Node<>(i,null);
                pre = first;
                continue;
            }
            //如果不是第一个
            Node<Integer> newNode = new Node<>(i, null);
            pre.next = newNode;
            pre = newNode;
            //最后一个结点，将下一个变为first
            if (i == 41){
                pre.next = first;
            }
        }
        //2.需要一个count计数器，模拟报数
        int count = 0;
        //3.遍历循环链表
        //记录每次遍历拿到的节点，默认从首结点开始
        Node<Integer> n = first;
        //记录当前结点的上一个结点
        Node<Integer> before = null;
        while (n != n.next){
            //模拟报数
            count++;
            //判断当前报数是否为3
            if (count == 3){
                //如果是3，删除节点，打印当前结点，重置count = 0，让n后移
                before.next = n.next;
                count = 0;
                System.out.print(n.item+",");
                n = n.next;
            }else {
                //如果不是3，让before变成当前结点，让当前结点后移
                before = n;
                n = n.next;
            }

        }
    }

    //节点类
    private static class Node<T> {
        //存储数据
        T item;
        //下一个节点
        Node next;

        public Node(T item, Node next){
            this.item = item;
            this.next = next;
        }
    }


}
